package com.my.study.structures.sort;

/**
 * @author Carlos
 * @version 1.0.0
 * @date 2023/2/23 22:06
 */
public class MyHeapSort {

    public static void main(String[] args) {
        int[] a = {1, 23, 2, 23, 2, 9};
        heapSortAsc(a);
        System.out.println(a);
    }
    
    private static void heapSortAsc(int[] a) {
        int n = a.length;

        for (int i = n / 2 - 1; i >= 0; i--) {
            maxHeapDown(a, i, n - 1);
        }

        for (int i = n - 1; i > 0; i--) {
            int tmp = a[0];
            a[0] = a[i];
            a[i] = tmp;
            
            maxHeapDown(a, 0, i- 1);
        }
        
        
    }
    
    private static void maxHeapDown(int[] a, int start, int end) {
        int p = start;
        int l = 2 * p + 1;
        int parent = a[p];

        for (; l <= end ; p = l, l = 2 * l + 1) {
            if (l < end && a[l] < a[l+1]) {
                l++;
            }
            
            if (parent > a[l]) {
                break;
            }
            else {
               a[p] = a[l];
               a[l] = parent;
            }
        }
    }
    
}
